import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class MaxPQ<Key> implements Iterable<Key> {
    
    private Key[] pq;
    private int n;
    private Comparator<Key> comparator;

    public MaxPQ(int initCapacity) {
        pq = (Key[]) new Object[initCapacity+1];
        n = 0;
    }

    public MaxPQ() {
        this(1);
    }

    public MaxPQ(int initCapacity, Comparator<Key> comparator) {

        pq = (Key[]) new Object[initCapacity+1];
        this.comparator = comparator;
        n = 0;
    }

    public MaxPQ(Comparator<Key> comparator) {
        this(1, comparator);
    }
    /* ? this local n shadows this.n ??  */
    /* type error !! */
    public MaxPQ(Key[] keys) {
        //int  n = keys.length;
        n = keys.length;
        pq = (Key[]) new Object[n+1];
        for(int i = 1; i <= n; i++) {
            pq[i] = keys[i-1];
        }
        for(int k = n/2; k>=1; k--)
            sink(k);
        assert isMaxHeap();
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public int size() {
        return n;
    }

    public Key max() {
        if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    private void resize(int capacity) {
        assert capacity > n;
        Key[] temp = (Key[])new Object[capacity+1];
        for(int i = 1; i <= n; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }

    public void insert(Key x) {
        if(n == pq.length - 1) resize( 2 * pq.length);
        
        pq[++n] = x;
        swim(n);
        assert isMaxHeap();
    }

    public Key delMax() {
        if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Key max = pq[1];
        exch(1, n--);
        sink(1);
        pq[n+1] = null;
        if(n > 0 && n == (pq.length-1)/4) resize(pq.length/2);
        assert isMaxHeap();
        return max;

    }

    private void swim(int k) {
        while(k > 1 && less(k/2, k)) {
            exch(k/2, k);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while(k * 2 <= n) {
            int j = k * 2;
            if(j < n && less(j, j+1)) j++;
            if(!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    private boolean less(int i, int j) {
        if(comparator == null) {
            return ((Comparable <Key>)pq[i]).compareTo(pq[j]) < 0;
        } else {
            return comparator.compare(pq[i], pq[j]) < 0; 
        }
    }

    private void exch(int i, int j) {
        Key tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
    }

    private boolean isMaxHeap() {
        for(int i = 1; i <=n ; i++) {
            if(pq[i] == null) return false;
        }
        for(int i = n+1; i < pq.length; i++) {
            if(pq[i] != null) return false;
        }

        if(pq[0] != null) return false;

        return isMaxHeapOrdered(1);
    }

    private boolean isMaxHeapOrdered(int k) {
        if(k > n) return true;
        int left = 2 * k; 
        int right = 2 * k + 1;
        if(left <= n && less(k, left)) return false;
        if(right <= n && less(k, right)) return false;

        return isMaxHeapOrdered(left) && isMaxHeapOrdered(right);
    }

    public Iterator<Key> iterator() {
        return new HeapIterator();
    }

    private class HeapIterator implements Iterator<Key> {
        private MaxPQ<Key> copy;

        public HeapIterator() {
            if(comparator == null) copy = new MaxPQ<Key>(size());
            else copy = new MaxPQ<Key>(size(), comparator);
            for(int i = 1; i <= n; i++) {
                copy.insert(pq[i]);
            }
        }
        public boolean hasNext() { return !copy.isEmpty();}
        public void remove() { throw new UnsupportedOperationException();}

        public Key next() {
            if(!hasNext()) throw new NoSuchElementException();
            return delMax();
        }
    }

    public static void main(String[] args) {
        MaxPQ<String> pq = new MaxPQ<String>();
        while(!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if(!item.equals("-")) pq.insert(item);
            else if(!pq.isEmpty()) StdOut.print(pq.delMax() + " ");
        }
        StdOut.println("(" + pq.size() + " left on pq)");

    }
}
